<!DOCTYPE html>
<html lang="zh-CN">
  <head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <meta name="description" content="">
  <meta name="keywords" content="">
  
    <link rel="icon" href="/avatar.jpg">
  
    
  <title>poj-2376 Cleaning Shifts | 科学君的不科学博客</title>
  <link rel="stylesheet" href="/style.css">
  <link rel="stylesheet" href="/lib/jquery.fancybox.min.css">
  <link href="https://maxcdn.bootstrapcdn.com/font-awesome/4.7.0/css/font-awesome.min.css">
  <script type="text/javascript" src="https://tajs.qq.com/stats?sId=65546304" charset="UTF-8"></script>
  <script>
  (function(){
      var bp = document.createElement('script');
      var curProtocol = window.location.protocol.split(':')[0];
      if (curProtocol === 'https') {
          bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
      }
      else {
          bp.src = 'http://push.zhanzhang.baidu.com/push.js';
      }
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(bp, s);
  })();
  </script>
</head>

<body>
  <header>
  <div class="header-container">
    <a class='logo' href="/">
      <span>科学君的不科学博客</span>
    </a>
    <ul class="right-header">
      
        <li class="nav-item">
          
            <a href="/" class="item-link">首页</a>
          
        </li>
      
        <li class="nav-item">
          
            <a href="/about" class="item-link">关于</a>
          
        </li>
      
        <li class="nav-item">
          
            <a href="/archives" class="item-link">归档</a>
          
        </li>
      
        <li class="nav-item">
          
            <a href="/tags" class="item-link">标签</a>
          
        </li>
      
        <li class="nav-item">
          
            <a href="/atom.xml" class="item-link">FEED 订阅</a>
          
        </li>
      
    </ul>
  </div>
</header>

  <main id='post'>
  <div class="content">
    <article>
      <section class="content markdown-body">
        <h1>poj-2376 Cleaning Shifts</h1>
        <div class='post-meta'>
          <i class="fa fa-calendar" aria-hidden="true"></i>
          <time>2016年07月13日</time>
          
          | <i class="fa fa-folder-open-o" aria-hidden="true"></i> 
  <div class="article-category">
    <a class="article-category-link" href="/categories/acm/">acm</a>
  </div>



          
          
          |
          
          <i class="fa fa-tag" aria-hidden="true"></i>
          
          
  <a href="/tags/#acm" class='tag'>acm</a>


          
        </div>
        <ul>
<li><a href="#sec-">题目：</a></li>
<li><a href="#sec-">代码：</a></li>
<li><a href="#sec-">解析&amp;吐槽：</a></li>
</ul>
<h1 id="题目："><a href="#题目：" class="headerlink" title="题目："></a>题目：<a id="sec-"></a></h1><p class="verse"><br>Cleaning Shifts<br><br>Time Limit: 1000MS        Memory Limit: 65536K<br><br>Total Submissions: 17287        Accepted: 4403<br><br><br><br>Description<br><br>Farmer John is assigning some of his N (1 &lt;= N &lt;= 25,000) cows to do some cleaning chores around the barn. He always wants to have one cow working on cleaning things up and has divided the day into T shifts (1 &lt;= T &lt;= 1,000,000), the first being shift 1 and the last being shift T.<br><br><br><br>Each cow is only available at some interval of times during the day for work on cleaning. Any cow that is selected for cleaning duty will work for the entirety of her interval.<br><br><br><br>Your job is to help Farmer John assign some cows to shifts so that (i) every shift has at least one cow assigned to it, and (ii) as few cows as possible are involved in cleaning. If it is not possible to assign a cow to each shift, print -1.<br><br><br><br>Input<br><br>\* Line 1: Two space-separated integers: N and T<br><br><br><br>\* Lines 2..N+1: Each line contains the start and end times of the interval during which a cow can work. A cow starts work at the start time and finishes after the end time.<br><br><br><br>Output<br><br>\* Line 1: The minimum number of cows Farmer John needs to hire or -1 if it is not possible to assign a cow to each shift.<br><br><br><br>Sample Input<br><br><br><br>3 10<br><br>1 7<br><br>3 6<br><br>6 10<br><br><br><br>Sample Output<br><br><br><br>2<br><br><br><br>Hint<br><br>This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.<br><br><br><br>INPUT DETAILS:<br><br><br><br>There are 3 cows and 10 shifts. Cow #1 can work shifts 1..7, cow #2 can work shifts 3..6, and cow #3 can work shifts 6..10.<br><br><br><br>OUTPUT DETAILS:<br><br><br><br>By selecting cows #1 and #3, all shifts are covered. There is no way to cover all the shifts using fewer than 2 cows.<br><br></p>

<h1 id="代码："><a href="#代码：" class="headerlink" title="代码："></a>代码：<a id="sec-"></a></h1><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// oj.cpp : 定义控制台应用程序的入口点。</span></span><br><span class="line"><span class="comment">//</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iomanip&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;sstream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;string&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;numeric&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;map&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;set&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;utility&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;map&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;list&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;functional&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bitset&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stack&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;deque&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;limits&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cmath&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> pair&lt;<span class="keyword">int</span>, <span class="keyword">int</span>&gt; P;</span><br><span class="line">P L[<span class="number">25010</span>];</span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">cmp</span><span class="params">(<span class="keyword">const</span> P&amp; l, <span class="keyword">const</span> P&amp; r)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (l.first == r.first)</span><br><span class="line">        <span class="keyword">return</span> l.second &gt; r.second;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        <span class="keyword">return</span> l.first &lt; r.first;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    ios::sync_with_stdio(<span class="literal">false</span>);</span><br><span class="line">    <span class="built_in">cin</span>.tie(<span class="literal">NULL</span>);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> N, T;</span><br><span class="line">    <span class="keyword">while</span> (<span class="built_in">cin</span> &gt;&gt; N &gt;&gt; T)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>;i &lt; N;++i)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">cin</span> &gt;&gt; L[i].first &gt;&gt; L[i].second;</span><br><span class="line">            <span class="comment">//if (L[i].first &gt; L[i].second)</span></span><br><span class="line">            <span class="comment">//	swap(L[i].first, L[i].second);</span></span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        sort(L, L + N<span class="comment">/*, cmp*/</span>);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> cnt = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">if</span> (L[<span class="number">0</span>].first &gt; <span class="number">1</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            cnt = <span class="number">-1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">int</span> start = <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">int</span> end = L[<span class="number">0</span>].second;</span><br><span class="line">            <span class="keyword">int</span> i = <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">while</span> (end &lt; T)</span><br><span class="line">            &#123;</span><br><span class="line">                <span class="keyword">if</span> (i &gt;= N)</span><br><span class="line">                &#123;</span><br><span class="line">                    cnt = <span class="number">-1</span>;</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line">                <span class="keyword">if</span> (L[i].second &lt;= end)</span><br><span class="line">                &#123;</span><br><span class="line">                    ++i;</span><br><span class="line">                    <span class="keyword">continue</span>;</span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line">                <span class="keyword">if</span> (L[i].first &lt;= start&amp;&amp;L[i].second &gt; end)</span><br><span class="line">                &#123;</span><br><span class="line">                    end = L[i].second;</span><br><span class="line">                    ++i;</span><br><span class="line">                    <span class="keyword">continue</span>;</span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line">                <span class="keyword">if</span> (L[i].first &gt; end + <span class="number">1</span>)</span><br><span class="line">                &#123;</span><br><span class="line">                    cnt = <span class="number">-1</span>;</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line">                ++cnt;</span><br><span class="line">                start = end + <span class="number">1</span>;</span><br><span class="line">                end = L[i].second;</span><br><span class="line">                ++i;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="built_in">cout</span> &lt;&lt; cnt &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h1 id="解析-amp-吐槽："><a href="#解析-amp-吐槽：" class="headerlink" title="解析&amp;吐槽："></a>解析&amp;吐槽：<a id="sec-"></a></h1><p>每一个节点都可以覆盖某个区间，选出最少的节点来覆盖指定的区间。明显的贪婪算法，但是有不少坑点。</p>
<p>首先，尽管题目没说，但是题目是有多组数据的！其次，如果上一个节点覆盖的区间是 i-j，下一个节点覆盖的区间可以从 j+1 开始。 最后，要覆盖的区间是从 1 开始，到 T 结束的。</p>
<p>在做题的时候也要注意几方面：题目可能会有无法覆盖整个区间的情况（无解），对于排过序的区间数据，如果第一个数据的区间左端点 大于 1 或者最后一个数据的右端点小于 T；就无解，如果遍历的时候不是以数据的索引作为循环变量的话，一定要注意判断是否达到的 最后一个数据。还要注意如果贪心策略是选择左端点不大于上一个选择的右端点（加一）的长度最大的区间，我的方法是如果判断下一 个数据比上一个更好的话，就更新记录的右端点，不自增计数。这样的话，排序的时候只需要考虑左端点，右端点不用管。我这里用 pair 来保存数据，它的比较函数会先比较 first 元素，在相等时再比较 second。我写的那个比较函数实际上是用不到的。还有我看到 有很多题解都会考虑输入数据中第一个比第二个大的情况，实测这个是不需要判断的，我注释掉了那段代码仍然可以 ac（见第 45 行）。</p>

      </section>
      <div class="license">
        <a href="http://creativecommons.org/licenses/by-sa/3.0/" rel="license" target="_blank">
          <img src="http://i.creativecommons.org/l/by-sa/3.0/88x31.png" style="border-width:0"
               alt="Creative Commons License" class="center">
        </a>
      </div>
      <p>
        本作品采用
        <a rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" target="_blank">
          署名-相同方式共享 4.0 国际
        </a>
        进行许可。欢迎转载、使用、重新发布，但务必保留文章署名
        “不科学的科学君” (Liu233w) 与博客链接：
        <a href="https://liu233w.github.io">https://liu233w.github.io</a>
        ，基于本文修改后的作品务必以相同的许可发布。如有任何疑问，请
        <a href="mailto:wwwlsmcom@outlook.com" target="_blank">与我联系</a>
        。
      </p>
    </article>
    
    <!-- disqus 评论框 start -->
    <div class="comment">
      <div id="disqus_thread" class="disqus-thread">
        <i>加载评论框需要翻墙</i>
      </div>
    </div>
    <!-- disqus 评论框 end -->
    
    
    <!-- livere 评论框 start -->
    <div class="comment">
      <div id="lv-container" data-id="city" data-uid="MTAyMC8zNTE5NS8xMTczMA=="></div>
    </div>
    <!-- livere 评论框 end -->
    
  </div>
  <aside>
    
    <div class="toc-container">
      <h1>目录</h1>
      <div class="content">
        <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#题目："><span class="toc-number">1.</span> <span class="toc-text">题目：</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#代码："><span class="toc-number">2.</span> <span class="toc-text">代码：</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#解析-amp-吐槽："><span class="toc-number">3.</span> <span class="toc-text">解析&amp;吐槽：</span></a></li></ol>
      </div>
    </div>
    
  </aside>
</main>

<!-- disqus 公共JS代码 -->
<script type="text/javascript">
  /* * * CONFIGURATION VARIABLES * * */
  var disqus_shortname = "liu233w";
  var disqus_identifier = "https://liu233w.github.io/2016/07/13/poj-2376.org/";
  var disqus_url = "https://liu233w.github.io/2016/07/13/poj-2376.org/";

  isAgent(getDisqus)

  // determine user agent in China
  function isAgent(cb) {
    var url = '//graph.facebook.com/feed?callback=h';
    var xhr = new XMLHttpRequest();
    var called = false;
    xhr.open('GET', url);
    xhr.onreadystatechange = function () {
      if (xhr.readyState === 4 && xhr.status === 200) {
        called = true;
        cb(true);
      }
    };
    xhr.send();
    // timeout 1s, this facebook API is very fast.
    setTimeout(function () {
      if (!called) {
        xhr.abort();
        cb(false)
      }
    }, 1000);
  }

  function getDisqus(isAgent) {
    var dsq = document.createElement('script');
    dsq.type = 'text/javascript';
    dsq.async = true
    dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
    (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq)
  }
</script>
<!-- disqus 公共JS代码 end -->


<script type="text/javascript">
  (function (d, s) {
    var j, e = d.getElementsByTagName(s)[0];

    if (typeof LivereTower === 'function') {
      return;
    }

    j = d.createElement(s);
    j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
    j.async = true;

    e.parentNode.insertBefore(j, e);
  })(document, 'script');
</script>


  <footer>
  <div class="copyright">
    <div>
      &copy; 2019 | Powered by <a href="https://hexo.io" target="_blank">Hexo</a>&nbsp
    </div>
    <div>
      Theme by <a href="https://github.com/lewis-geek/hexo-theme-Aath" target="_blank">Aath</a>
    </div>
  </div>
</footer>


<script src="https://cdn.bootcss.com/jquery/3.2.1/jquery.min.js"></script>
<script src="/lib/in-view.min.js"></script>
<script src="/lib/lodash.min.js"></script>
<script>
  var isDown = true
  var oldY = 0
  inView.offset(50)

  document.body.addEventListener('touchstart', function(){});
  
  window.addEventListener('scroll', _.throttle(e => {
    var currentY = window.scrollY
    if((oldY - currentY) < 0) {
      isDown = true
    } else {
      isDown = false
    }
    oldY = currentY
  }, 250))

  $("article img").each(function() {
      var strA = "<a data-fancybox='gallery' href='" + this.src + "'></a>";
      $(this).wrapAll(strA);
  });

  $('.toc-link').each(function() {
      var href = $(this).attr("href");
      
      inView(href).on('exit', () => {
        if (isDown) {
          handleActive(href)
        }
      })

      inView(href).on('enter', () => {
        if (!isDown) {
          handleActive(href)
        }
      })

      this.onclick = function(e) {
        var pos = $(href).offset().top - 10;
        $("html,body").animate({scrollTop: pos}, 300);
        setTimeout(() => {
          handleActive(href)
        }, 350)
        return false
      }
  })

  function handleActive(href) {
    document.querySelectorAll('.toc-link').forEach(elm => {
      elm.classList.remove('active')
    })
    document.querySelector(".toc [href='"+ href +"']").classList.add('active')
  }
</script>
<script src="/lib/jquery.fancybox.min.js"></script>

<script async src="//dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>

</body>
</html>
